﻿<!DOCTYPE html>
<html>
<head>
<title>第4章：算法与流程控制</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<style type="text/css">
/* GitHub stylesheet for MarkdownPad (http://markdownpad.com) */
/* Author: Nicolas Hery - http://nicolashery.com */
/* Version: b13fe65ca28d2e568c6ed5d7f06581183df8f2ff */
/* Source: https://github.com/nicolahery/markdownpad-github */

/* RESET
=============================================================================*/

html, body, div, span, applet, object, iframe, h1, h2, h3, h4, h5, h6, p, blockquote, pre, a, abbr, acronym, address, big, cite, code, del, dfn, em, img, ins, kbd, q, s, samp, small, strike, strong, sub, sup, tt, var, b, u, i, center, dl, dt, dd, ol, ul, li, fieldset, form, label, legend, table, caption, tbody, tfoot, thead, tr, th, td, article, aside, canvas, details, embed, figure, figcaption, footer, header, hgroup, menu, nav, output, ruby, section, summary, time, mark, audio, video {
  margin: 0;
  padding: 0;
  border: 0;
}

/* BODY
=============================================================================*/

body {
  font-family: Helvetica, arial, freesans, clean, sans-serif;
  font-size: 16px;
  line-height: 1.6;
  color: #333;
  background-color: #fff;
  padding: 20px;
  max-width: 960px;
  margin: 0 auto;
}

@media screen and (max-width: 768px) {
  body {
  	font-size: 20px !important;
  }
}

body>*:first-child {
  margin-top: 0 !important;
}

body>*:last-child {
  margin-bottom: 0 !important;
}

/* BLOCKS
=============================================================================*/

p, blockquote, ul, ol, dl, table, pre {
  margin: 16px 0;
}

/* HEADERS
=============================================================================*/

h1, h2, h3, h4, h5, h6 {
  margin: 20px 0 10px;
  padding: 0;
  font-weight: bold;
  -webkit-font-smoothing: antialiased;
}

h1 tt, h1 code, h2 tt, h2 code, h3 tt, h3 code, h4 tt, h4 code, h5 tt, h5 code, h6 tt, h6 code {
  font-size: inherit;
}

h1 {
  font-size: 28px;
}

h1:first-of-type {
  font-size: 32px;
  text-align: center;
}

h2 {
  font-size: 26px;
}

h3 {
  font-size: 22px;
}

h4 {
  font-size: 18px;
}

h5 {
  font-size: 16px;
}

h6 {
  font-size: 14px;
}

body>h2:first-child, body>h1:first-child, body>h1:first-child+h2, body>h3:first-child, body>h4:first-child, body>h5:first-child, body>h6:first-child {
  margin-top: 0;
  padding-top: 0;
}

a:first-child h1, a:first-child h2, a:first-child h3, a:first-child h4, a:first-child h5, a:first-child h6 {
  margin-top: 0;
  padding-top: 0;
}

h1+p, h2+p, h3+p, h4+p, h5+p, h6+p {
  margin-top: 10px;
}

/* LINKS
=============================================================================*/

a {
  color: #4183C4;
  text-decoration: none;
}

a:hover {
  color: #d0782a;
  text-decoration: underline;
}

a:active {
  color: #bd4147;
}

/* LISTS
=============================================================================*/

ul, ol {
  padding-left: 30px;
}

ul li > :first-child, 
ol li > :first-child, 
ul li ul:first-of-type, 
ol li ol:first-of-type, 
ul li ol:first-of-type, 
ol li ul:first-of-type {
  margin-top: 0px;
  margin-bottom: 0px;
}

ul ul, ul ol, ol ol, ol ul {
  margin-bottom: 0;
}

dl {
  padding: 0;
}

dl dt {
  font-size: 14px;
  font-weight: bold;
  font-style: italic;
  padding: 0;
  margin: 15px 0 5px;
}

dl dt:first-child {
  padding: 0;
}

dl dt>:first-child {
  margin-top: 0px;
}

dl dt>:last-child {
  margin-bottom: 0px;
}

dl dd {
  margin: 0 0 15px;
  padding: 0 15px;
}

dl dd>:first-child {
  margin-top: 0px;
}

dl dd>:last-child {
  margin-bottom: 0px;
}

/* CODE
=============================================================================*/

pre, code, tt {
  font-family: Consolas, "Liberation Mono", Courier, monospace;
}

code, tt {
  margin: 0 0px;
  padding: 0px 3px;
  white-space: nowrap;
  border: 1px solid #eaeaea;
  background-color: #eee;
  color: #00d;
  border-radius: 3px;
}

pre>code {
  margin: 0;
  padding: 0;
  white-space: pre;
  border: none;
  background: transparent;
}

pre {
  background-color: #f8f8f8;
  border: 1px solid #ccc;
  line-height: 19px;
  overflow: auto;
  padding: 6px 10px;
  border-radius: 3px;
}

pre code, pre tt {
  background-color: transparent;
  border: none;
}

kbd {
    -moz-border-bottom-colors: none;
    -moz-border-left-colors: none;
    -moz-border-right-colors: none;
    -moz-border-top-colors: none;
    background-color: #DDDDDD;
    background-image: linear-gradient(#F1F1F1, #DDDDDD);
    background-repeat: repeat-x;
    border-color: #DDDDDD #CCCCCC #CCCCCC #DDDDDD;
    border-image: none;
    border-radius: 2px 2px 2px 2px;
    border-style: solid;
    border-width: 1px;
    font-family: "Helvetica Neue",Helvetica,Arial,sans-serif;
    line-height: 16px;
    padding: 1px 4px;
}

/* QUOTES
=============================================================================*/
blockquote {
  border-left: 4px solid #42b983;
  padding: 0 15px;
  color: #d1d9e1;
  background: #474949;
}

blockquote>:first-child {
  margin-top: 0px;
}

blockquote>:last-child {
  margin-bottom: 0px;
}

/* HORIZONTAL RULES
=============================================================================*/

hr {
  clear: both;
  margin: 15px 0;
  height: 0px;
  overflow: hidden;
  border: none;
  background: transparent;
  border-bottom: 4px solid #ddd;
  padding: 0;
}

/* TABLES
=============================================================================*/
table {
	margin: 0 auto;
	border-collapse: collapse;
	width: 100%;
	box-sizing: border-box;
	margin-bottom: 30px;
	
}

table th, table td {
  border: 1px solid #ccc;
  padding: 6px 13px; 
}

table th {
  font-weight: bold;
  text-align: center !important;
  background-color: #9ec68e;
}

table tr {
  border-top: 1px solid #ccc;
  background-color: #fff;
}

table tr:nth-child(2n) {
  background-color: #dff0d8;
}

/* IMAGES
=============================================================================*/
img {
  max-width: 100%;
}

p > img {
  display: table;
  margin: 0 auto;
}
</style>
<style type="text/css">
.highlight  { background: #ffffff; }
.highlight .c { color: #999988; font-style: italic } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { font-weight: bold } /* Keyword */
.highlight .o { font-weight: bold } /* Operator */
.highlight .cm { color: #999988; font-style: italic } /* Comment.Multiline */
.highlight .cp { color: #999999; font-weight: bold } /* Comment.Preproc */
.highlight .c1 { color: #999988; font-style: italic } /* Comment.Single */
.highlight .cs { color: #999999; font-weight: bold; font-style: italic } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .gd .x { color: #000000; background-color: #ffaaaa } /* Generic.Deleted.Specific */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #999999 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .gi .x { color: #000000; background-color: #aaffaa } /* Generic.Inserted.Specific */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #aaaaaa } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { font-weight: bold } /* Keyword.Constant */
.highlight .kd { font-weight: bold } /* Keyword.Declaration */
.highlight .kp { font-weight: bold } /* Keyword.Pseudo */
.highlight .kr { font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #445588; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #009999 } /* Literal.Number */
.highlight .s { color: #d14 } /* Literal.String */
.highlight .na { color: #008080 } /* Name.Attribute */
.highlight .nb { color: #0086B3 } /* Name.Builtin */
.highlight .nc { color: #445588; font-weight: bold } /* Name.Class */
.highlight .no { color: #008080 } /* Name.Constant */
.highlight .ni { color: #800080 } /* Name.Entity */
.highlight .ne { color: #990000; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #990000; font-weight: bold } /* Name.Function */
.highlight .nn { color: #555555 } /* Name.Namespace */
.highlight .nt { color: #000080 } /* Name.Tag */
.highlight .nv { color: #008080 } /* Name.Variable */
.highlight .ow { font-weight: bold } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mf { color: #009999 } /* Literal.Number.Float */
.highlight .mh { color: #009999 } /* Literal.Number.Hex */
.highlight .mi { color: #009999 } /* Literal.Number.Integer */
.highlight .mo { color: #009999 } /* Literal.Number.Oct */
.highlight .sb { color: #d14 } /* Literal.String.Backtick */
.highlight .sc { color: #d14 } /* Literal.String.Char */
.highlight .sd { color: #d14 } /* Literal.String.Doc */
.highlight .s2 { color: #d14 } /* Literal.String.Double */
.highlight .se { color: #d14 } /* Literal.String.Escape */
.highlight .sh { color: #d14 } /* Literal.String.Heredoc */
.highlight .si { color: #d14 } /* Literal.String.Interpol */
.highlight .sx { color: #d14 } /* Literal.String.Other */
.highlight .sr { color: #009926 } /* Literal.String.Regex */
.highlight .s1 { color: #d14 } /* Literal.String.Single */
.highlight .ss { color: #990073 } /* Literal.String.Symbol */
.highlight .bp { color: #999999 } /* Name.Builtin.Pseudo */
.highlight .vc { color: #008080 } /* Name.Variable.Class */
.highlight .vg { color: #008080 } /* Name.Variable.Global */
.highlight .vi { color: #008080 } /* Name.Variable.Instance */
.highlight .il { color: #009999 } /* Literal.Number.Integer.Long */
.pl-c {
    color: #969896;
}

.pl-c1,.pl-mdh,.pl-mm,.pl-mp,.pl-mr,.pl-s1 .pl-v,.pl-s3,.pl-sc,.pl-sv {
    color: #0086b3;
}

.pl-e,.pl-en {
    color: #795da3;
}

.pl-s1 .pl-s2,.pl-smi,.pl-smp,.pl-stj,.pl-vo,.pl-vpf {
    color: #333;
}

.pl-ent {
    color: #63a35c;
}

.pl-k,.pl-s,.pl-st {
    color: #a71d5d;
}

.pl-pds,.pl-s1,.pl-s1 .pl-pse .pl-s2,.pl-sr,.pl-sr .pl-cce,.pl-sr .pl-sra,.pl-sr .pl-sre,.pl-src,.pl-v {
    color: #df5000;
}

.pl-id {
    color: #b52a1d;
}

.pl-ii {
    background-color: #b52a1d;
    color: #f8f8f8;
}

.pl-sr .pl-cce {
    color: #63a35c;
    font-weight: bold;
}

.pl-ml {
    color: #693a17;
}

.pl-mh,.pl-mh .pl-en,.pl-ms {
    color: #1d3e81;
    font-weight: bold;
}

.pl-mq {
    color: #008080;
}

.pl-mi {
    color: #333;
    font-style: italic;
}

.pl-mb {
    color: #333;
    font-weight: bold;
}

.pl-md,.pl-mdhf {
    background-color: #ffecec;
    color: #bd2c00;
}

.pl-mdht,.pl-mi1 {
    background-color: #eaffea;
    color: #55a532;
}

.pl-mdr {
    color: #795da3;
    font-weight: bold;
}

.pl-mo {
    color: #1d3e81;
}
.task-list {
padding-left:10px;
margin-bottom:0;
}

.task-list li {
    margin-left: 20px;
}

.task-list-item {
list-style-type:none;
padding-left:10px;
}

.task-list-item label {
font-weight:400;
}

.task-list-item.enabled label {
cursor:pointer;
}

.task-list-item+.task-list-item {
margin-top:3px;
}

.task-list-item-checkbox {
display:inline-block;
margin-left:-20px;
margin-right:3px;
vertical-align:1px;
}
</style>
<base target=_blank>
</head>
<body>
<h1 id="-4-">第4章：算法与流程控制</h1>
<h2 id="-">循环的类型</h2>
<p><code>for</code>循环是JS中最常用的循环结构。它由四部分组成：初始化、前测条件、后执行体、循环体。</p>
<blockquote>
<p>在<code>for</code>循环初始化中的<code>var</code>语句创建一个函数级的变量，JS只有函数级作用域，因此在<code>for</code>循环中定义一个变量相当于在循环体外定义一个新变量。</p>
</blockquote>
<h2 id="-">循环性能</h2>
<p>在JS提供的四种循环类型中，只有<code>for-in</code>循环比其他明显要慢。</p>
<p>由于每次迭代操作同时搜索实例或原型属性，<code>for-in</code>循环的每次迭代都会产生更多开销，所以比其他循环类型要慢。</p>
<blockquote>
<p>不要使用<code>for-in</code>来遍历数组成员。</p>
</blockquote>
<p>如果循环类型与性能无关，有两个可选因素：</p>
<ol>
<li>每次迭代处理的事物</li><li>迭代的次数</li></ol>
<p><strong>减少迭代的工作量</strong></p>
<blockquote>
<p>一个提升循环整体速度的好方法是限制循环中耗时操作的数量。</p>
</blockquote>
<p>优化循环的第一步是要减少对象成员及数组项的查找次数。</p>
<p><strong>基于函数的迭代</strong></p>
<p>原生数组方法：<code>forEach()</code>，此方法遍历一个数组的所有成员，并在每个成员上执行一个函数。要运行的函数作为参数传给<code>forEach()</code>，并在调用时接收三个参数，分别是：当前数组项的值、索引以及数组本身。</p>
<pre><code>items.forEach(function (value, index, array) {
    process(value);
});
</code></pre><p>尽管基于函数的迭代提供了一个更为便利的迭代方法，但它仍然比基于循环的迭代要慢一些。对每个数组项调用外部方法所带来的开销是速度慢的主要原因。在所有情况下，基于循环的迭代比基于函数的迭代快<strong>8</strong>倍。</p>
<h2 id="-">条件语句</h2>
<p><strong><code>if-else</code>对比<code>switch</code></strong></p>
<p>使用<code>if-else</code>还是<code>switch</code>，最流行的方法是基于测试条件的数量来选择：条件数量越大，越倾向于使用<code>switch</code>。</p>
<p>事实证明，大多数情况下<code>switch</code>比<code>if-else</code>运行的更快，但只有当条件数量很大时才快得明显。这两个语句主要性能区别是：当条件增加时，<code>if-else</code>性能负担增加的程度比<code>switch</code>要多。</p>
<h3 id="-if-else-">优化<code>if-else</code></h3>
<p>优化<code>if-else</code>的目标是：最小化到达正确分支前所需判断的条件数量。最简单的优化方法是确保最可能出现的条件放在首位。</p>
<p><code>if-else</code>中的条件语句应该总是按照从最大概率到最小概率的顺序排列，以确保运行速度最快。</p>
<p>另一种减少条件判断次数的方法是把<code>if-else</code>组织成一系列嵌套的<code>if-else</code>语句。使用单个庞大的<code>if-else</code>通常会导致运行缓慢，因为每个条件都需要判断。</p>
<h2 id="-">查找表</h2>
<p>有时候优化条件语句的最佳方案是避免使用<code>if-else</code>和<code>switch</code>。当有大量离散值需要测试时，<code>if-else</code>和<code>switch</code>比使用查找表慢很多。JS中可以使用数组和普通对象来构建查找表，通过查找表访问数据会快很多。</p>
<p>当使用查找表时，必须完全抛弃条件判断语句。这个过程变成数组项查询或对象成员查询。查找表的一个主要有点是：不用书写任何条件判断语句，即便候选值数量增加时，也几乎不会产生额外的性能开销。</p>
<h2 id="-">递归</h2>
<p>递归函数的潜在问题是终止条件不明确或缺少终止条件会导致函数长时间运行，并使得用户界面处于假死状态。而且递归函数还可能遇到浏览器的“调用栈大小限制”。</p>
<h3 id="-">调用栈限制</h3>
<p>JS引擎支持的递归数量与JS调用栈大小直接相关。只有IE例外，它的调用栈与系统空闲内存有关。</p>
<h3 id="-">递归模式</h3>
<p>当遇到调用栈大小限制时，第一步先检查代码中的递归实例。</p>
<p>有两种递归模式值得注意：第一种是直接递归模式，第二种是隐伏模式。大多数调用栈错误都与这两种模式有关。最常见的导致栈溢出的原因是不正确的终止条件，因此定位模式错误的第一步是验证终止条件。</p>
<h2 id="-">迭代</h2>
<p>任何递归实现的算法同样可以用迭代来实现。迭代算法通常包含几个不同的循环，分别对应计算过程的不同方面。使用优化后的循环替代长时间运行的递归函数可以提升性能。</p>
<h2 id="memoization">Memoization</h2>
<p>减少工作量是最好的优化技术。<strong>Memoization</strong>是一种避免重复工作的方法，它缓存前一个计算结果供后续计算使用，避免了重复工作。</p>

</body>
</html>
<!-- This document was created with MarkdownPad, the Markdown editor for Windows (http://markdownpad.com) -->
